package com.algorithm.commonsort;

/**
 * Created with IntelliJ IDEA.
 * User: LK
 * Date: 2018/4/2
 * Time: 19:48
 * To change this template use File | Settings | File Templates.
 * Description: 归并排序
 */
public class MergeSort {

    public static void main(String[] args) {

        int test[]={3,7,1,28,46,16};
        int lenth=test.length;
        mergeSort(test,0,lenth-1);
        for(int i=0;i<lenth;i++)
            System.out.print(test[i]+",");
    }

    /**
     *  把目标数组通过递归调用变成两个有序数组
     * @param arr 数组
     * @param s 数组初始下标
     * @param e 数组结束下标
     */
    public static void mergeSort(int[] arr,int s,int e){
        if(s<e){
            int mid=(s+e)/2;
            mergeSort(arr,s,mid);//分成单个数，然后在合并
            mergeSort(arr,mid+1,e);
            sort(arr,s,mid,e);
        }
    }

    /**
     *  归并排序方法
     * @param arr 要排序的数组
     * @param s 数组起始下标
     * @param mid 数组下标中间值
     * @param e 数组结束下标
     */
    public static void sort(int[] arr,int s,int mid,int e){
        int i,j,k,n1,n2;    //
        n1=mid-s+1;   //前面数组长度
        n2=e-mid;     //后面数组长度
        //初始化前后两个数组
        int[] l=new int[n1];
        int[] r=new int[n2];
        //把要排序的数组前后两部分分别给自己创建的数组赋值
        for(i=0,k=s;i<n1;i++,k++)
            l[i]=arr[k];
        for(i=0,k=mid+1;i<n2;i++,k++)
            r[i]=arr[k];
        //判断两个有序数组同一下标的大小，值大的放到原数组arr中，同时移动所赋值数组的下标
        for(k=s,i=0,j=0;i<n1&&j<n2;k++){
            if(l[i]>r[j]){
                arr[k]=l[i];
                i++;
            }
            else{
                arr[k]=r[j];
                j++;
            }
        }
        //当一个数组遍历完所有所有元素，则跳出上面循环，把另一个没有遍历完的数组顺序放到目标数组arr中
        if(i<n1){
            for(j=i;j<n1;j++,k++)
                arr[k]=l[j];
        }
        if(j<n2){
            for(i=j;i<n2;i++,k++)
                arr[k]=r[i];
        }
    }

}

